package features.advance.leetcode.array.easy;

/**
 *  剑指 Offer 39. 数组中出现次数超过一半的数字
 *
 *  难度：简单
 *
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 *
 *
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
 * 输出: 2
 *
 *
 * 限制：
 *
 * 1 <= 数组长度 <= 50000
 *
 *
 *
 * 注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/
 *
 * @author LIN
 * @date 2021-05-31
 */
public class Offer39 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int majorityElement(int[] nums) {

                int votes = 1,temp = nums[0];

                for (int num : nums) {
                    if(votes == 0){
                        temp = num;
                        votes++;
                    }else  if(temp != num){
                        votes--;
                    }else{
                        votes++;
                    }
                }
                return temp;
            }
        };
        int[] nums = {1,2,3,2,2,2,5,4,2};
        int res = solution.majorityElement(nums);
        System.out.println(res);

    }


    static class Solution {
        public int majorityElement(int[] nums) {
            int x=0,vec=0;
            for (int num : nums) {
                if(vec == 0){
                    x = num;
                }
                vec += num == x ?1:-1;
            }
            return x;
        }
    }
}
